The present invention relates to a catalyst for effecting hydrodealkylation of alkylaromatic compounds and a process for producing the catalyst. More particularly, this invention relates to a catalyst for hydrodealkylation of alkylaromatic compounds comprising the complex compounds formed from either (a) graphite and (b) an alkali metal or (a) graphite, (b) an alkali metal and (c) at least one compound of a metal selected from the group consisting of Group VIII of the Periodic Table. According to effecting the use of the catalyst of this invention, Ar-C.sub.n.sub.-1 H.sub.2n.sub.-1 may be selectively produced from Ar-C.sub.n H.sub.2n.sub.+1, wherein Ar is an aromatic radical.